package calculate;

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;


public class FibonacciSequence {


    public static void main(String[] args) {
        System.out.println("��������ô���");
        Scanner scanner = new Scanner(System.in);
        long a = scanner.nextLong();
        System.out.println(fibonacci(a));
        //System.out.println(tailFibonacci(a,0));
    }


    /**
     * ʹ��β�ݹ�ʵ��쳲�����������
     * f(n) = f(n-1) + f(n-2)
     * 1 1 2 3 5 8 13
     *
     * @param k
     * @return
     */
    private static long fibonacci(long k) {
        if(k == 0 || k == 1){
            k++;
            return k;
        }else {
            return fibonacci(k-1) + fibonacci(k-2);
        }
    }


    /**
     * ʹ��β�ݹ���쳲���������
     * @param pre:���ϴβ�ѯ���
     * @param res:��һ�ν��
     * @param n:����
     * @return
     */
    private static long tailFibonacci(long pre,long res,int n) {
        if(n == 0 || n == 1){
            n++;
            return res;
        }else {
            return tailFibonacci(res,pre + res,n-1);
        }
    }


}
